package acwing.贪心;

import java.util.Arrays;
import java.util.Scanner;

/**
 * k == n 全选
 * k < n
 * k是偶数
 *  1.k个数全是负数 >= 0
 *  2.负数是奇数个 选偶数个负数再n里面在选一个正数 >= 0
 * k < n
 * k是奇数
 *  3.k个数全是负数 < 0
 *  4.至少有一个数是正数 >= 0
 *  2和4是同一种情况
 *
 * @author yang
 * @date 2021/12/17
 */
public class 乘积最大 {

    static int N = 100010;
    static int mod = 1000000009;
    static int[] arr = new int[N];
    static int n;
    static int k;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        Arrays.sort(arr,0,n);
        long res = 0;
        int l = 0 ,r = n - 1;
        int sign = 1; // 正负
        // 奇数
        if ((k % 2) == 1) {
            res = arr[r--];
            k--;
            // 情况4
            if (res < 0) {
                sign = -1;
            }
        }
        while (k != 0) {
            long x = (long) arr[l] * arr[l + 1];
            long y = (long) arr[r] * arr[r - 1];
            if (x * sign > y * sign) {
                res = x % mod * res % mod;
                l += 2;

            } else {
                res = y % mod * res % mod;
                r -= 2;
            }
            k -= 2;
        }
        System.out.println(res);
    }
}
